package tsp;

import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.Map.Entry;

import javax.swing.text.StyledEditorKit.BoldAction;

import mvc.GraphOpt;
import ilog.concert.IloException;
import ilog.concert.IloLinearNumExpr;
import ilog.concert.IloNumVar;
import ilog.cplex.IloCplex;
import ilog.cplex.IloCplex.DoubleParam;

/**
 * Classe Programme Linéaire
 * 
 * @author Amin Zheng Gishan
 * 
 */
public class PL {
	IloCplex cplex;
	IloNumVar[][] x;
	IloLinearNumExpr objective;
	IloLinearNumExpr constraints1;
	IloLinearNumExpr constraints2;
	IloLinearNumExpr subtours;
	int n;

	public PL(Double[][] couts) {
		n = couts.length;
		try {
			cplex = new IloCplex();
			
			//cplex.setParam(IloCplex.IntParam.TimeLimit, 0.5);
			//cplex.setParam(DoubleParam.EpInt, 0.0);
			
			// si le nombre de ville est supérieur à 80, on ajoute ces paramètres
			if(n>=80){
				cplex.setParam(IloCplex.IntParam.IntSolLim,2);
				cplex.setParam(IloCplex.IntParam.Threads, 1);
			}
			
			cplex.setOut(null);
			cplex.setWarning(null);
			x = new IloNumVar[n][];
			
			
			for (int i = 0; i < n; i++) {
				x[i] = cplex.boolVarArray(n);
			}
			objective = cplex.linearNumExpr();
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					objective.addTerm(couts[i][j], x[i][j]);
				}
			}
			cplex.addMinimize(objective);

			for (int i = 0; i < n; i++) {
				constraints1 = cplex.linearNumExpr();
				for (int j = 0; j < n; j++) {
					if (i != j) {
						constraints1.addTerm(1.0, x[i][j]);
					}
				}
				cplex.addEq(constraints1, 1.0);
			}

			for (int j = 0; j < n; j++) {
				constraints2 = cplex.linearNumExpr();
				for (int i = 0; i < n; i++) {
					if (j != i) {
						constraints2.addTerm(1.0, x[i][j]);
					}
				}
				cplex.addEq(constraints2, 1.0);
			}

		} catch (IloException e) {
			e.printStackTrace();
		}

	}


	public GraphOpt solve() {

		GraphOpt g = new GraphOpt();
		try {
			boolean go = false;
			double[][] solution = new double[n][n];
			
			cplex.setOut(null);

			while (!go) {

				if (cplex.solve()) {
					for (int i = 0; i < n; i++) {
						double[] sol = cplex.getValues(x[i]);
						solution[i] = sol;
					}
					System.out.println("value :"+cplex.getObjValue());
				}
				g = sous_tours(solution);	
				if(g.getChemin().size()>0){
					go=true;
				}
				else{
					g=null;
				}
			}
			System.out.println("cout cplex : "+cplex.getObjValue());
			g.setCout(cplex.getObjValue());
			System.out.println(g.getChemin());
			System.out.println(cplex.getStatus());
			System.out.println("cout "+g.getCout());

			cplex.end();
		} catch (IloException e) {
			e.printStackTrace();
		}
		return g;
	}
	
	 public GraphOpt sous_tours(double[][] soluCplex) throws IloException {
          
		 GraphOpt g = new GraphOpt();
		 int num = 0; 
	  for (int i = 0; i < soluCplex.length; i++) { 
		  LinkedList<Integer> liste = new LinkedList<Integer>(); subtours = cplex.linearNumExpr();
	  
		  if (!appartient(g.getListSubtours(), i)) {
	  
			  liste.add(i); 
			  Integer tempo; 
			  tempo = i;
	  
			  while ((getSuivant(soluCplex, tempo) != null) && (!liste.contains(getSuivant(soluCplex, tempo))))  {
	
				  tempo = getSuivant(soluCplex, tempo); 
				  liste.add(tempo);
			  } 
			  if ((liste.get(0)==getSuivant(soluCplex, tempo))) { liste.add(liste.getFirst()); }
	  
			  if (liste.size() - 1 == soluCplex.length) { 
				  g.getChemin().addAll(liste);
				  return g; 
			  } else
			  {   
				  g.getListSubtours().put(num, liste); num++;
				  subtours = cplex.linearNumExpr();
				  	for (int i1 = 0; i1 < liste.size() - 1; i1++) { 
				  		subtours.addTerm(1.0, x[liste.get(i1)][liste.get(i1 + 1)]); 
				  	} cplex.addLe(subtours,liste.size() - 2); 
		      }
	 } } return g; }
	 

	
	public boolean appartient(
			HashMap<Integer, LinkedList<Integer>> map_sous_tours, Integer point) {

		if (map_sous_tours.size() > 0) {
			for (Entry<Integer, LinkedList<Integer>> entry : map_sous_tours
					.entrySet()) {
				Integer key = entry.getKey();
				LinkedList<Integer> value = entry.getValue();

				if (value.contains(point)) {
					return true;
				}
			}
		}
		return false;
	}

	public Integer getSuivant(double[][] tab, int i) {
		for (int j = 0; j < tab.length; j++) {
			if (tab[i][j] > 0 && tab[i][j] != Double.MAX_VALUE)
				return j;
		}
		return null;
	}

}
